#include <bits/stdc++.h>
#include <cstring>
#include <string>
#include <iostream>
#include <sstream>
#include <fstream>
#include <stdio.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000;
//拓展欧几里得  已知a,b 求满足ax + by = gcd(a, b) 的一组解
int exgcd(int a, int b, int &x, int &y)
{
	if (b == 0){
		x = 1;
		y = 0;
                	return a;
    	}
    	int ans = exgcd(b, a % b, x, y);
    	int tmp = x;
    	x = y;
    	y = tmp - a / b * y;
    	return ans;
}
// 暴力找出200 ~ MAX_N 的所有质数
void get_Prime_Number(int *Prime, int &cnt)
{
	cnt = 0;
    	for (int i = 201;i < MAX_N; i+=2){
        		bool flag = false;
               		for (int j = 2;(j * j) <= i; j++){
                		if (i % j == 0){
                			flag = true;
                			break;
            			}
        		}
        		if (!flag) Prime[cnt++] = i;
    	}
}
//RSA初始化
void RSA_Initialize(int &n, int &e, int &d)
{
 	int Prime[MAX_N], cnt = 0;
    	get_Prime_Number(Prime, cnt);
	srand((unsigned)time(NULL));
    	int r1 = rand() % cnt;
    	int r2 = rand() % cnt;
    	int p1 = Prime[r1], p2 = Prime[r2]; // 随机取两个质数.
    	n = p1 * p2; // 计算n
    	int  m = (p1 - 1) * (p2 - 1);
    	int y;
    	// 选择一个与n互质的元素,记为e,求得模反元素d
    	for (int i = 3; i < m; i += 1331){
        		int gcd = exgcd(i, m, d, y);
       		 if (gcd == 1 && d > 0){
            			e = i;
            			break;
        		}
    	}
}
// 快速幂求 a^b % c
int Quick_Pow(int a, int b, int c)
{
    	int tot = 1;
    	while (b){
        		if (b & 1) tot = (1LL * tot * a) % c; //可能会溢出
        		a = (1LL * a * a) % c;
        		b >>= 1;
   	 }
    	return tot;
}

void RSA_Encrypt(int e,int n,string str,string &output)
{
	ostringstream oss;
	string result;
  	int len=str.size();
  	for(int i=0;i<len;i++){
  		int tot=Quick_Pow(str[i],e,n);
  		//cout<<tot<<" ";
  		oss<<tot<<" ";
  	}
  	output=oss.str();
}
string RSA_Decrypt(int d,int n,string str)
{
	istringstream iss(str);
        ostringstream oss;
        string res;
	int x;
	while(iss>>x){
		oss<<(char)Quick_Pow(x,d,n);
	}
	res=oss.str();
        return res;
}
/**
int main()
{
	string str;
	string output="";
	ofstream fout("key.txt");
	ifstream fin;
	int n,e,d;
	RSA_Initialize(n,e,d);
	fout<<d<<" "<<n;
	fout.close();
	fin.open("key.txt");
	getline(cin,str);
	RSA_Encrypt(e,n,str,output);
	int d1,n1;
	fin>>d1>>n1;
	cout<<RSA_Decrypt(d1,n1,output)<<endl;
	fin.close();
	return 0;
}**/